class Solution
{
public:
    long long countInterestingSubarrays(vector<int> &nums, int modulo, int k)
    {
        int n = nums.size();
        vector<int> prefixModKCount(n + 1, 0);
        for (int i = 0; i < n; ++i)
        {
            prefixModKCount[i + 1] = prefixModKCount[i] + (nums[i] % modulo == k);
        }

        long long ans = 0;
        unordered_map<int, int> countModCount;
        countModCount[0] = 1;
        for (int i = 1; i <= n; ++i)
        {
            long long modCount = prefixModKCount[i];
            long long targetModCount = (modCount + modulo - k) % modulo;
            ans += countModCount[targetModCount];
            ++countModCount[modCount % modulo];
        }

        return ans;
    }
};